Vào ngày 1 tháng 1 năm 1872, Đức hoàng Wilhelm I chuyển Bộ Hải quân của Phổ thành Bộ Hải quân Đế quốc Đức, đồng thời bổ nhiệm Stosch làm Bộ trưởng mới của bộ. Mặc dù tướng Stosch trước đây không có kinh nghiệm về các vấn đề hải quân, ông đã có những đóng góp lớn đến việc tổ chức lực lượng Hải quân Đức. Ông đã từng nói với một người bạn của mình: "Ông biết rằng chính hải quân thì không kích động tôi nhưng sự độc đáo và khó nhọc của công việc thì có". Về cơ bản, với kế hoạch phát triển hải quân, gọi là Flottengründungsplan, do ông đề ra vào năm 1873, ông vẫn duy trì chiến lược hải quân của Đức. Theo kế hoạch của mình, ông tiếp tục nhấn mạnh việc phòng ngự bờ biển như một sứ mệnh hàng đầu của hải quân, điều này cho thấy nhận thức của ông không khác với lý luận của Roon về nước Đức như là một cường quốc hải quân hạng hai và cả quan điểm của Bismarck (mặc dù ông là một địch thủ chính trị của vị Thủ tướng). Lục quân vẫn là lực lượng quân sự tối ưu của Đức. Như Eberhard von Mantey đã chỉ ra, Stosch hiểu rằng sức mạnh của Đế quốc Đức chỉ nằm ở một cái đầu lưỡi lê của lục quân, và "điều này hoàn toàn là dĩ nhiên vì lục quân đã hoàn thành thắng lợi công cuộc thống nhất đế quốc". Và, để thực hiện sứ mệnh hàng đầu của hải quân, Stosch đã chủ trương xây dựng tàu thuyền, và ông còn có các khẩu đội pháo nổi và monitor để phòng vệ vùng lãnh hải của Đức, các tuần dương hạm để bảo vệ quyền lợi của Đức ở hải ngoại, cũng như các tuần phòng hạm và hộ vệ hạm để thực hiện các chiến dịch phối hợp.[3][6]

Trong suốt 11 năm tại nhiệm ở Bộ Hải quân Đức, Stosch đã hoàn thành 4 dự án chiến hạm mà ông thừa hưởng và khởi đầu 6 dự án chiến hạm khác, trong đó có 2 chiếc là Kaiser và Deutschland được xây dựng ở Anh. Tất cả đều không bì được những tàu chiến lớn nhất và tân tiến nhất của các hải quân hàng đầu của châu Âu. Các chiến hạm xây dựng ở Đức lệ thuộc nặng nề vào bộ phận của Anh hoặc là công nghệ Anh được chuyển giao có phép cho các nhà sản xuất của Đức. Đế quốc Đức non trẻ ban đầu không có thuộc địa nhưng có đội thương thuyền lớn thứ ba thế giới, vì thế họ cần những tàu chiến có chức năng tuần tra để giương cờ nước ở hải ngoại: Stosch đã đáp ứng nhu cầu này bằng việc bổ sung cho lực lượng hải quân 8 hộ vệ hạm bọc sắt và 3 pháo hạm sắt. Từ sự khởi đầu khiêm tốn này, Stosch đã đặt nền móng trong hải quân Đức trở thành một trong những hải quân hàng đầu thế giới trong những năm trước Chiến tranh thế giới thứ nhất. Sau khi hai chiến hạm Kaiser và Deutschland được hoàn tất, cho đến khi nhiệm kỳ của ông kết thúc, tất cả các chiến hạm của Đức đều được xây dựng ở các âu thuyền Đức, và Stosch cũng dần dần thoát khỏi sự lệ thuộc vào Anh về việc bọc thiết giáp. Mặc dù hãng Krupp ở Essen không sản xuất thiết giáp trước năm 1890, ngay từ đầu hãng đã cung cấp mọi khẩu pháo của hạm đội Đức đồng thời tiếp liệu cho các hải quân Nga, Áo-Hung và một số hải quân khác. Tập đoàn Krupp đã trở thành một thế lực lớn trong nền công nghiệp hậu cần hải quân đến mức mà các nhà sản xuất hàng đầu của Anh và Pháp phải gắng sức để đuổi kịp.[3][7]

Stosch cũng chú trọng xây dựng các viện nghiên cứu của ngành hải quân. Dưới thời ông, Đài Quan sát Hải quân Đức và Nha Thủy Văn học đã được thiết lập. Để cải thiện chất lượng tồi tệ của sĩ quan hải quân Phổ (năm 1861, thuyền buồm nhỏ Amazone đã bị đắm và tất cả các học viên hải quân đều thiệt mạng), một học viện hải quân đã được thành lập tại Kiel. Kế hoạch huấn luyện sĩ quan tham mưu được đề xuất, và nhiều trạm hải quân được thiết lập ở khắp nơi[4]. Ngoài ra, thời kỳ ông làm Bộ trưởng cũng cho thấy Hải quân Đế quốc Đức áp dụng kiểu chào quân sự chính thức của Quân đội Phổ[8]. Ông cũng áp dụng kỷ luật khắt khe của Lục quân Phổ vào Hải quân và điều này vấp phải sự chống đối của các sĩ quan hải quân cao niên.

Vào đầu thập niên 1880, Đức thực sự đã theo kịp hoặc là vượt Anh và Pháp về số lượng chiến hạm. Ngay từ năm 1873, lực lượng hải quân Đức đã đủ mạnh để cung cấp tàu thuyền để hỗ trợ cho một nỗ lực của Anh nhằm khống chế biển Địa Trung Hải trong cuộc nội chiến ở Tây Ban Nha khi đó. Hàng tá năm sau đó, khi Đức giành được thuộc địa tại châu Phi và Thái Bình Dương, đã dùng đến các tàu tuần dương bọc sắt được chế tạo dưới thời Stosch. Stosch giữ chức Bộ trưởng Bộ Hải quân cho đến năm 1883, tuy nhiên 5 năm cuối thời ông đánh dấu những khủng hoảng và tai tiếng, khởi đầu với việc một tàu chiến mới, SMS Grosser Kurfürst, bị đắm do một vụ va chạm vào tháng 5 năm 1878. Sự kiện này đã cướp đi sinh mạng của 276 người, đã đem đến cho dư luận một hình ảnh xấu về lực lượng hải quân, và tạo điều kiện cho nhiều địch thủ của ông gây áp lực buộc Stosch phải từ chức. Stosch đã làm cho tình hình trở nên tồi tệ hơn khi ông cố gắng che chở cho phe cánh của mình và sa thải những sĩ quan mà ông cho là "bất trung". Mặc dù Stosch vẫn giữ chặt cái ghế Bộ trưởng Bộ Hải quân của mình khi Bismarck đòi huyền chức ông, sự kiên nhẫn của ông không đem lại điều gì tốt đẹp cho hải quân. Trong 5 năm này, kinh phí hải quân suy giảm và không một chiến hạm mới nào được chế tạo. Nhưng nhờ vào những dự án đã được khởi công trong những năm đầu tại chức của ông, nước Đức đã có được lực lượng hải quân thiết giáp lớn thứ ba thế giới.[3][4][7] Ngư lôi của Đức cũng tốt nhất thế giới, chít ít là về mặt chất lượng. Stosch đã đặt nền tảng cho một hệ thống phòng ngự tích cực bờ biển đúng đắn với các tàu ngư lôi và đủ tàu thiết giáp để hình thành một "hạm đội phá vây", có thể phá dỡ vòng phong tỏa nếu như Hải quân Anh phong tỏa bờ biển Đức. Sự ra đi của ông vào năm 1883 đã gây tiếc nuối cho phần lớn đội ngũ sĩ quan hải quân Đức, trong đó có Đô đốc tương lai Alfred von Tirplitz.[9]

SMS Stosch, một hộ vệ hạm thuộc lớp Bismarck, đã được đặt lườn vào năm 1876 tại xưởng đóng tàu của hãng Vulcan AG ở Stettin. Nó được hạ thủy vào năm 1877 và nhập biên chế vào năm 1878.